package SearchAlgorithm;

// 插值查找
public class InterpolationSearch {
    public int interpolationSearch(int[] arr, int left, int right, int target){
        while(left <= right){
            // 跟二分查找唯一一行不同之处
            int mid = left + ((target - arr[left]) / (arr[right] - arr[left])) * (right - left);
            if(target > arr[mid]){
                left = mid + 1;
            }else if(target < arr[mid]){
                right = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        InterpolationSearch is = new InterpolationSearch();
        int[] nums = new int[]{1,3,5,6,8,21,23,24,30};
        System.out.println(is.interpolationSearch(nums,0,nums.length-1,23));

    }
}
